package com.cuz.daileetcode;

import com.cuz.daileetcode.utils.TreeNode;

public class Day33 {


    /******
     * 找两个节点的最低公共父节点
     * 1.分两种情况思考，
     *  1.1 node1 是node2 的祖先节点 or node2 是node1的祖先节点
     *  1.2 node1 和node2存在相同的祖先节点
     * @param root 根节点
     * @param node1 节点1
     * @param node2 节点2
     * @return TreeNpde
     */
    public static TreeNode findLowestAncestor(TreeNode root, TreeNode node1, TreeNode node2) {
        if (root == null || root == node1 || root == node2) {
            return root;
        }
        TreeNode left = findLowestAncestor(root.left, node1, node2);
        TreeNode right = findLowestAncestor(root.right, node1, node2);
        //如果都不为null 返回root自己
        if (left != null && right != null) {
            return root;
        }
        //左右两棵树存在一个为null
        if (left == null) {
            return right;
        } else {
            return left;
        }
    }
}
